Home > Search Results: keywords:"conflict free colouring"
Search:
Search Tips :: Advanced Search
Search collections:
Sort by: Display results: Output format:
National Repository of Grey Literature 1 records found  Search took 0.01 seconds. 
Parity vertex colorings
 Soukup, Jan ; Gregor, Petr (advisor) ; Kučera, Petr (referee)
A parity path in a vertex colouring of a graph G is a path in which every colour is used even number of times. A parity vertex colouring is a vertex colouring having no parity path. Let χp(G) be the minimal number of colours in a parity vertex colouring of G. It is known that χp(Bn) ≥ √ n where Bn is the complete binary tree with n layers. We show that the sharp inequality holds. We use this result to obtain a new bound χp(T) > 3 √ log n where T is any binary tree with n vertices. We study the complexity of computing the parity chromatic number χp(G). We show that checking whether a vertex colouring is a parity vertex colouring is coNP-complete and we design an exponential algorithm to com- pute it. Then we use Courcelle's theorem to prove the existence of a FPT algorithm checking whether χp(G) ≤ k parametrized by k and the treewidth of G. Moreover, we design our own FPT algorithm solving the problem. This algorithm runs in polynomial time whenever k and the treewidth of G is bounded. Finally, we discuss the relation of this colouring to other types of colourings, specifically unique maximum, conflict free, and parity edge colourings.
Detailed record

Interested in being notified about new results for this query?
Subscribe to the RSS feed.
Digital Repository :: Search :: Submit :: Personalize :: Help
Powered by Invenio v1.1.2
Maintained by admin.invenio@techlib.cz
This site is also available in the following languages:
Česky  English